//
// Created by 周智超 on 2020/7/16.
//

#include <stdio.h>
#include <stdlib.h>

  struct Node {
      int val;
      int numChildren;
      struct Node** children;
  };


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void lengthAndLevel(struct Node* root, int *returnSize, int *level)
{
    if(root == NULL)
    {
        return ;
    }
    int tmpLevel = 0, maxLevel = 0;
    for(int i = 0; i < root->numChildren; i++)
    {
        lengthAndLevel(root->children[i], returnSize, &tmpLevel);
        if(tmpLevel > maxLevel)
        {
            maxLevel = tmpLevel;
        }
        tmpLevel = 0;
    }
    (*returnSize)++;
    *level = maxLevel + 1;

}
void initColumnSizes(struct Node * root, int level, int *returnColumnSizes)
{
    if(root == NULL)
    {
        return ;
    }
    returnColumnSizes[level] += 1;
    for(int i = 0; i < root->numChildren; i++)
    {
        initColumnSizes(root->children[i], level + 1, returnColumnSizes);
    }
}
int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
    int level = 0;
    int length = 0;
    *returnSize = 0;
    lengthAndLevel(root, &length, &level);
    printf("%d,%d\n", length, level);
    *returnSize = level;
    int **res = NULL;
    *returnColumnSizes = (int *)malloc(sizeof(int) * level);
    if(length == 0)
    {
        return res;
    }
    for(int i = 0; i < level; i++)
    {
        (*returnColumnSizes)[i] = 0;
    }
    initColumnSizes(root, 0, *returnColumnSizes);
    res = (int **)malloc(sizeof(int *) * level);
    for(int i = 0; i < level; i++)
    {
        res[i] = (int *)malloc(sizeof(int) * (*returnColumnSizes)[i]);
    }
    struct Node* queue[10000];
    int front = 0;
    int rear = 0;
    int levelIndex = 0;
    int *levelCounter = (int *)malloc(sizeof(int) * level);
    for(int i = 0; i < level; i++)
    {
        levelCounter[i] = 0;
    }
    queue[rear++] = root;
    struct Node* tmp;
    while(front != rear)
    {
        tmp = queue[front];
        printf("%d,%d, %d, %d\n", tmp->val, levelIndex, front,rear);
        front = (front + 1) ;
        res[levelIndex][levelCounter[levelIndex]] = tmp->val;
        levelCounter[levelIndex]++;
        if(levelCounter[levelIndex] >= (*returnColumnSizes)[levelIndex])
        {
            levelIndex++;
        }
        for(int i = 0; i < tmp->numChildren; i++)
        {
            queue[rear] = tmp->children[i];
            rear = (rear + 1) ;
        }
    }
    free(levelCounter);
    return res;
}

int main()
{
    struct Node n;
    n.val = 44;
    n.numChildren = 0;
    int returnSize;
    int* returnColumnSizes;
    levelOrder(&n, &returnSize, &returnColumnSizes);
}

